#include <vector>
#include <stdfix.h>
#include <iostream>
using namespace std;
template<typename T>
void show(T arr[], int len) {
    for (int i = 0; i < len; i++)
        cout << arr[i] << " ";
    cout << endl;
    //cout<<"@@@@" << endl;
}

template<typename T> // 整数、浮点数都可以使用
void merge_sort(T arr[], int len) {
    T *a = arr;
    T *b = new T[len];
    for (int seg = 1; seg < len; seg += seg) {
        for (int start = 0; start < len; start += seg + seg) {
            int low = start, mid = min(start + seg, len), high = min(start + seg + seg, len);
            int k = low;
            int start1 = low, end1 = mid;
            int start2 = mid, end2 = high;
            cout<<"seg="<<seg << ",start=" << start << ",mid=" << mid << ",high=" << high <<endl;
            show(b, len);
            while (start1 < end1 && start2 < end2)
                b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
            while (start1 < end1)
                b[k++] = a[start1++];
            while (start2 < end2)
                b[k++] = a[start2++];
        }
        T *temp = a;
        a = b;
        b = temp;
        //show(a, len);
        cout<<"-----------" << endl;
    }
    if (a != arr) {
        for (int i = 0; i < len; i++)
            b[i] = a[i];
        b = a;
    }
    delete[] b;
}
int main() {
    int arr[]= { 61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62 }; 
    int len=sizeof(arr)/sizeof(arr[0]);
    merge_sort(arr, len);
    show(arr,len); 
    float arrf[]= { 17.5, 19.1, 0.6, 1.9, 10.5, 12.4, 3.8, 19.7, 1.5, 25.4, 28.6, 4.4, 23.8, 5.4 }; 
    int lenf=sizeof(arrf)/sizeof(arrf[0]);
    merge_sort(arrf,lenf);
    
    show(arrf,lenf); 
    return 0;
}